/**
  Implementacja dynamicznego słownika
  część projektu z wyszukiwania informacji
*/
#include<stdio.h>
#include<stdlib.h>
#define assert(X) {if(!(X)){printf("assertion failed on line %d\n >>%s\n", __LINE__, #X);exit(1);}}

struct Node {
  struct Node **child;
  char *character;
  int val;
  char count;
  char mem;
};

typedef struct Node Node;

Node* createNode() {
  Node *ret = malloc ( sizeof ( Node ) );
  ret->character = malloc ( 4 * sizeof ( char ) );
  ret->child = malloc ( 4 * sizeof ( Node* ) );
  ret->count = 0;
  ret->mem = 4;
  ret->val = -1;
  return ret;
}

// zwraca numer, -1 jeżeli nie ma
int get ( Node *node, char *word ) {
  if ( * ( word ) == 0 )
    return node->val;
  int i = 0;
  for ( i = 0; i < node->count; ++i ) {
    if ( node->character[i] == *word ) break;
  }
  if ( i >= node->count ) return -1;
  return get ( node->child[i], word+1 );
}

// jeżeli słowa nie ma - dodaje z value i zwraca value
// jeżeli jest - zwraca jego wartość
int set ( Node *node, char *word, int value ) {
  if ( * ( word ) == 0 ) {
    if ( node-> val == -1 ) node->val = value;
    return node->val;
  }
  int i = 0;
  for ( i = 0; i < node->count; ++i ) {
    if ( node->character[i] == *word ) break;
  }
  if ( i == node->count ) {
    if ( node->count == node->mem ) {
      node->mem += 4;
      node->child = realloc ( node->child, node->mem * sizeof ( Node* ) );
      node->character = realloc ( node->character, node->mem * sizeof ( char ) );
    }
    node->character[i] = *word;
    node->child[i] = createNode();
    ++node->count;
  }
  return set ( node->child[i], word+1, value );
}

// liczy ilosc nodow
int countNodes ( Node *node ){
  int ret = 1;
  int i = 0;
  for ( i = 0; i < node->count; ++i ) {
    ret += countNodes ( node->child[i] );
  }
  return ret;
}

// liczy ilosc nietrywialnych nodow
// trywialne to te, ktore by wywalila kompresja sciezki
int countBubaNodes ( Node *node ){
  int ret = 1;
  int i = 0;
  if ( node->count == 1 && node->child[0]->count <= 1 ){
    return countBubaNodes ( node->child[0] ); //< minus jeden na child[0]
  }
  
  for ( i = 0; i < node->count; ++i ) {
    ret += countBubaNodes ( node->child[i] );
  }
  return ret;
}

// liczy ilosc znakow we wszystkich nodach
int countChars ( Node *node ){
  int ret = node->count;
  int i = 0;
  for ( i = 0; i < node->count; ++i ) {
    ret += countChars ( node->child[i] );
  }
  return ret;
}

// zapisuje do pliku wg formatu opisanego dalej
void dumpNodes ( FILE *file, Node *node ){
  //fprintf ( file, "%d %d ", node->val, node->count );
  fwrite ( &node->val, sizeof(int), 1, file );
  fwrite ( &node->count, sizeof(char), 1, file );
  
  int i;
  for ( i = 0; i < node->count; ++i ) {
    dumpNodes ( file, node->child[i] );
  }
}

// zapisuje znaki do pliku
void dumpChars ( FILE *file, Node *node ){
  fwrite ( node->character, 1, node->count, file );
  int i;
  for ( i = 0; i < node->count; ++i ) {
    dumpChars ( file, node->child[i] );
  }
}

// ustawia synow w kolejnosci alfabetycznej
void sortNodes ( Node *node ){
  int i, j, dummy;
  Node *dummyNode;
  
  for ( i = 0; i < node->count; ++i ){
    for ( j = i+1; j < node->count; ++j ){
      if ( node->character[i] > node->character[j] ){
        dummy = node->character[i];
        dummyNode = node->child[i];
        node->character[i] = node->character[j];
        node->child[i] = node->child[j];
        node->character[j] = dummy;
        node->child[j] = dummyNode;
      }
    }
  }
  for ( i = 0; i < node->count; ++i ) sortNodes ( node->child[i] );
}

/**
 *
 *  Interfejs zaczyna się tu
 *
 */


Node *base = NULL;

/// Zwraca wartość, jeżeli nie zdefiniowana zwraca -1
int getVal ( char *word ) {
    int temp = get ( base, word );
    //printf("node zwraca %d\n",temp);
  return temp;
}

/// Nadaje wartość słowu 
/// Jeżeli słowa jeszcze nie było zwraca nową wartość
/// Jeżeli była, to zwraca wartość nadaną wcześniej
int setVal ( char *word ) {
  static int next = 1;
  if ( base == NULL ) base = createNode();
  int ret = set ( base, word, next );
  if ( ret == next ) ++next;
  //printf("setval %d\n", ret);
  return ret;
}


/// Zrzuca strukturę do pliku
/// Format pliku:
/// [ilość nodów] [ilość znaków]
/// [opis noda]
/// [znaki]
///
/// [opis noda] =  wartości [value] [n = ilość synów] w preorder
/// [znaki] = tablice znaków w preorder
/// dodatkowo w każdym nodzie tablice znaków są posortowane
void serialize ( char *filename ){
  assert ( base != NULL );
  sortNodes ( base );
  printf("sort ok \n");
  int n = countNodes ( base );
  int m = countChars ( base );
  int v = countBubaNodes ( base );
  printf("count ok\n");
  printf("buba = %d\n", v);
  FILE *file = fopen ( filename, "wb" );
  assert ( file != NULL );
//  fprintf( file, "%d %d\n", n, m );
  fwrite ( &n, sizeof(int), 1, file );
  fwrite ( &m, sizeof(int), 1, file );
  dumpNodes ( file, base );
  printf("nodes dumped ok\n");
//  fprintf( file, "\n" );
  dumpChars ( file, base );
  printf("chars dumped ok\n");
//  fprintf( file, "\nbuba = %d\n", v );
  fclose ( file );
}
